package primaryAlgorithm.countAndSay;
/**
 * @Date 2020/03/19
 * @author 王光浩
 * @Thinking 采用类似与层序遍历的方式，使用迭代实现
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n）
 */
import java.util.LinkedList;

public class MyMethodOne {
	  public String countAndSay(int n) {
		  if(n--==1)return "1";
		  LinkedList<Integer> queue=new LinkedList<Integer>();  //使用栈来存储
		  queue.add(1); //初始值
		  //求第n项
		  while(n>0) {
			  int size=queue.size();
			  //根据第n-1层求第n层
			  int value=queue.poll();
			  int count=1;
			  for(int i=1;i<size;i++) {
				  int top=queue.poll();
				  if(value!=top) {
					  queue.add(count);queue.add(value);
					  value=top;
					  count=1;
				  }
				  else
					  count++;
			  }
			  queue.add(count);queue.add(value);
			  n--;
		  }
		  StringBuilder res=new StringBuilder();
		  for(int tem:queue) {
			  res.append(tem);
		  }
		  return res.toString();
	  }
}
